Developments concerning error correction codes of data have been actively performed for high-density recording of a semiconductor memory device that records digital data in a NAND flash memory section.
An error correction code is given to data by an error-code generation circuit (an encoder) before recording. It is detected whether an error is present in data read out by an error detection and correction circuit (a decoder). When an error is present, the data is corrected.
A correction ability can be increased by increasing the number of bits of the error correction code. However, a circuit size increases and processing speed decreases. Further, various errors such as a random error, a burst error, and a mixed error of the random error and the burst error occur.
In order to efficiently perform appropriate error correction, it is effective to use two or more codes in combination. As a combining method for the codes, there is known a product code in which linear codes having a relatively small correction ability, for example, BCH (Bose-Chaudhuri-Hocquenghem) codes are arrayed in n dimensions.
A two-dimensional product-code is explained with reference to FIG. 1. In coding processing, data of (M×N) bits are arrayed as N data segmented in units of M bits (a block 1). First, coding by a correction code C1 is applied to each of data of M bits in a row direction. That is, a correction code C1 (a C1 parity) of P bits is added to each of the data of M bits. Consequently, N pieces of C1 coded data having a code length of P bits are formed. The number of bits of the entire correction code C1 (the C1 parity) is P×N (a block 2).
Subsequently, coding in a column direction in which C1 coded data (the block 1+the block 2) of ((M+P)×N) bits are segmented in units of N bits is performed. In the coding, a correction code C2 (a C2 parity) of Q bits is added to each of data of N bits. The number of bits of the entire correction code C2 (the C2 parity) is (M+P)×Q (a block 3). Consequently, a product-coded data of ((M+P)×(N+Q)) bits as a whole is formed. FIG. 1 is an example in which the size of a crossing section of a row and a column is 1. However, in some case, the crossing section size is larger than 1.
In decoding processing of the product code, it is necessary to alternately iterate decoding in the row direction and the column direction. For example, first, decoding in the row direction is performed. However, if uncorrectable data is present, the data is not changed. Subsequently, decoding in the column direction is performed on the basis of data corrected in the decoding in the row direction. If uncorrectable data is present, the data is not changed. The decoding in the row direction is performed again on the basis of the data corrected in the decoding in the column direction. Data uncorrectable in the row-direction decoding of the last time is sometimes corrected. Similarly, the next decoding in the column direction is performed on the basis of the corrected data. This iterative process continues until the entire data is corrected or the data is determined as uncorrectable.